#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> ans;
vector<int> track;
int bucket;
void dfs(vector<int>& candidates, int start, int target) {
    if (bucket == target) {
        ans.push_back(track);
        return;
    }
    for (int i = start; i < candidates.size(); i++) {
        if (candidates[i] > target - bucket) continue;
        // 拿几个第start个元素
        int most = (target - bucket) / candidates[i];
        for (int j = 1; j <= most; j++) {
            bucket += j * candidates[i];
            for (int k = 0; k < j; k++) track.push_back(candidates[i]);
            dfs(candidates, i + 1, target);
            // 退还回去
            bucket -= j * candidates[i];
            for (int k = 0; k < j; k++) track.pop_back();
        }
    }
    return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    if(candidates.size() == 1){
        if(candidates[0] > target) return vector<vector<int>> {};
        else if(target % candidates[0] == 0){
            int cnt = target / candidates[0];
            for(int i=0;i<cnt;i++) track.push_back(candidates[0]);
            ans.push_back(track);
            return ans;
        }else return  vector<vector<int>> {};
    }
    sort(candidates.begin(), candidates.end(),
         [](int a, int b) { return a > b; });
    int cur = 0;
    while (cur < candidates.size() && candidates[cur] > target) cur++;
    if(cur == candidates.size()) return vector<vector<int>> {};
    candidates = vector<int>(candidates.begin() + cur, candidates.end());
    dfs(candidates, 0, target);
    return ans;
}